package collection;

import java.util.Iterator;

public class AdjGraph<V, E> implements IGraph<V, E> {

	private HashSet<Vertex<V,E>> vertices = new HashSet<Vertex<V,E>>();
	private HashSet<Edge<E,V>> edges = new HashSet<Edge<E,V>>();

	public AdjGraph(){}
	
	@Override
	public boolean isEmpty() 
	{
		return vertices.isEmpty();
	}

	@Override
	public Vertex<V,E> createVertex(V element) 
	{
		return new Vertex<V,E>(element);
	}

	@Override
	public Edge<E,V> createEdge(E element, Vertex<V,E> v1, Vertex<V,E> v2) 
	{
		return new Edge<E,V>(element, v1, v2);
	}
	
	@Override
	public Edge<E, V> createEdge(Vertex<V, E> v1, Vertex<V, E> v2) 
	{
		return new Edge<E,V>(v1, v2);
	}

	@Override
	public void addVertex(Vertex<V,E> vertex) 
	{
		vertices.add(vertex);
	}

	@Override
	public void addEdge(Edge<E,V> edge) 
	{
		edges.add(edge);
	}
	
	@Override
	public Vertex<V,E> addVertexElement(V element) 
	{
		Vertex<V,E> v = createVertex(element);
		addVertex(v);
		return v;
	}

	@Override
	public Edge<E,V> addEdgeElement(E element, Vertex<V, E> v1, Vertex<V, E> v2)
	{
		Edge<E,V> e = createEdge(element, v1, v2);
		addEdge(e);
		return e;
	}
	
	@Override
	public Edge<E,V> addEdge(Vertex<V, E> v1, Vertex<V, E> v2) 
	{
		Edge<E,V> e = createEdge(v1, v2);
		addEdge(e);
		return e;
	}

	@Override
	public void removeVertex(Vertex<V,E> vertex) 
	{
		if (vertex.hasNoEdges())
		{
			this.vertices.remove(vertex);
		}
		else
		{
			throw new IllegalArgumentException("There are edges associated with this vertex!");
		}
	}

	@Override
	public void removeEdge(Edge<E,V> edge) 
	{
		for (Vertex<V,E> v : edge.getVertices())
		{
			v.removeEdge(edge);
		}
		this.edges.remove(edge);
	}

	@Override
	public HashSet<Edge<E,V>> incidentEdges(Vertex<V,E> vertex) 
	{
		return vertex.getEdges();
	}

	@Override
	public HashSet<Vertex<V,E>> endVertices(Edge<E,V> edge) 
	{
		return edge.getVertices();
	}
	
	@Override
	public boolean hasEdge(Vertex<V, E> vertex, Edge<E,V> edge) 
	{
		return vertex.hasEdge(edge);
	}

	@Override
	public boolean hasVertex(Edge<E, V> edge, Vertex<V,E> vertex) 
	{
		return edge.hasVertex(vertex);
	}

	@Override
	public Vertex<V,E> oppositeVertex(Edge<E,V> edge, Vertex<V,E> vertex) 
	{
		return edge.oppositeVertex(vertex);
	}

	@Override
	public Iterator<Vertex<V,E>> vertices() 
	{
		return vertices.iterator();
	}

	@Override
	public Iterator<Edge<E,V>> edges() 
	{
		return edges.iterator();
	}

	@Override
	public int vertexCount() 
	{
		return vertices.size();
	}

	@Override
	public int edgeCount() 
	{
		return edges.size();
	}

	@Override
	public String toString()
	{
		String retStr = "";
		
		for (Vertex<V,E> v : vertices)
		{
			retStr += v + " : ";
			for (Edge<E,V> e : v.getEdges())
			{
				retStr += e + " ";
			}
			retStr += "\n";
		}
		
		return retStr;
	}
	
	public void resetVertexAndEdgeStatus()
	{
		for (Vertex<V,E> v : vertices)
		{
			v.isVisited = false;
		}
		
		for (Edge<E,V> e : edges)
		{
			e.type = EdgeType.DISCOVERY;
		}
	}

	private boolean findPath(ListStack<Edge<E, V>> edgeStack, Vertex<V, E> source, Vertex<V, E> dest) 
	{
		source.isVisited = true;
		
		for (Edge<E,V> edge : this.incidentEdges(source))
		{
			Vertex<V,E> otherVertex = oppositeVertex(edge, source);
			if (otherVertex.isVisited)
			{
				edge.type = EdgeType.BACK;
			}
			else
			{
				edgeStack.push(edge);
				if (otherVertex == dest)
					return true;
				else
				{
					if (findPath(edgeStack, otherVertex, dest))
						return true;
					else
					{
						edgeStack.pop();
					}
						
				}
			}
		}
		return false;
	}
	
	public UnOrdTree<Vertex<V,E>> depthFirstSearchTree(Vertex<V,E> startV)
	{
		UnOrdTree<Vertex<V,E>> tree = new UnOrdTree<Vertex<V,E>>();
		tree.createRoot(startV);
		createDepthFirstSearchTree(tree, tree.getRoot());
		return tree;
	}
	
	private void createDepthFirstSearchTree(UnOrdTree<Vertex<V,E>> tree, UnOrdTreeNode<Vertex<V, E>> vertexNode) 
	{
		Vertex<V,E> vertex = vertexNode.getElement();
		vertex.isVisited = true;
		
		for (Edge<E,V> edge : incidentEdges(vertex))
		{
			Vertex<V,E> otherVertex = edge.oppositeVertex(vertex);
			if (otherVertex.isVisited)
			{
				edge.type = EdgeType.BACK;
			}
			else
			{
				UnOrdTreeNode<Vertex<V,E>> otherVertexNode = tree.createNode(otherVertex);
				tree.addChild(vertexNode, otherVertexNode);
				createDepthFirstSearchTree(tree, otherVertexNode);
			}
		}
	}

	public void performDepthFirstSearch(Vertex<V, E> vertex) 
	{
		vertex.isVisited = true;
		
		for (Edge<E,V> edge : incidentEdges(vertex))
		{
			Vertex<V,E> otherVertex = edge.oppositeVertex(vertex);
			if (otherVertex.isVisited)
			{
				edge.type = EdgeType.BACK;
			}
			else
			{
				performDepthFirstSearch(otherVertex);
			}
		}
	}
	
	public UnOrdTree<Vertex<V,E>> breathFirstSearchTree(Vertex<V,E> startV)
	{
		UnOrdTree<Vertex<V,E>> tree = new UnOrdTree<Vertex<V,E>>();
		tree.createRoot(startV);
		createBreathFirstSearchTree(tree, tree.getRoot());
		return tree;
	}
	
	private void createBreathFirstSearchTree(UnOrdTree<Vertex<V,E>> tree, UnOrdTreeNode<Vertex<V, E>> vertexNode) 
	{
		ListQueue<UnOrdTreeNode<Vertex<V,E>>> vQueue = new ListQueue<UnOrdTreeNode<Vertex<V,E>>>();
		vQueue.enqueue(vertexNode);

		while(!vQueue.isEmpty())
		{
			UnOrdTreeNode<Vertex<V,E>> vNode = vQueue.dequeue();
			Vertex<V,E> v = vNode.getElement();
			v.isVisited = true;
			for (Edge<E,V> edge : incidentEdges(v))
			{
				Vertex<V,E> otherV = edge.oppositeVertex(v);
				if (otherV.isVisited)
				{
					edge.type = EdgeType.CROSS;
				}
				else
				{
					UnOrdTreeNode<Vertex<V,E>> otherVNode = tree.createNode(otherV);
					tree.addChild(vNode, otherVNode);
					vQueue.enqueue(otherVNode);
				}
			}
		}
	}
	
	public void performBreathFirstSearch(Vertex<V, E> vertex) 
	{
		ListQueue<Vertex<V,E>> vQueue = new ListQueue<Vertex<V,E>>();
		vQueue.enqueue(vertex);

		while(!vQueue.isEmpty())
		{
			Vertex<V,E> v = vQueue.dequeue();
			v.isVisited = true;
			for (Edge<E,V> edge : incidentEdges(v))
			{
				Vertex<V,E> otherV = edge.oppositeVertex(v);
				if (otherV.isVisited)
				{
					edge.type = EdgeType.CROSS;
				}
				else
				{
					vQueue.enqueue(otherV);
				}
			}
		}
	}
	
	public SLinkedList<Edge<E,V>> findPath(Vertex<V, E> source, Vertex<V, E> dest) 
	{
		SLinkedList<Edge<E,V>> retList = new SLinkedList<Edge<E,V>>();
		ListStack<Edge<E,V>> edgeStack = new ListStack<Edge<E,V>>();
		findPath(edgeStack, source, dest);

		while(!edgeStack.isEmpty())
		{
			retList.addLast(retList.createNode(edgeStack.pop()));
		}
		retList.reverse();
		
		return retList;
	}

	public HashSet<HashSet<Vertex<V, E>>> connectedComponents() 
	{
		HashSet<HashSet<Vertex<V, E>>> retSet = new HashSet<HashSet<Vertex<V, E>>>();
		if (isEmpty())
			return retSet;
		
		Vertex<V,E> vertex = vertices.iterator().next();
		HashSet<Vertex<V, E>> unvisitedVertices = new HashSet<Vertex<V, E>>();
		for (Vertex<V,E> v : vertices)
		{
			unvisitedVertices.add(v);
		}

		while (!unvisitedVertices.isEmpty()) 
		{
			HashSet<Vertex<V, E>> component = new HashSet<Vertex<V, E>>();
			ListQueue<Vertex<V,E>> vQueue = new ListQueue<Vertex<V,E>>();
			vQueue.enqueue(vertex);
			while (!vQueue.isEmpty()) 
			{
				Vertex<V, E> v = vQueue.dequeue();
				v.isVisited = true;
				unvisitedVertices.remove(v);
				component.add(v);
				for (Edge<E, V> edge : incidentEdges(v)) 
				{
					Vertex<V, E> otherV = edge.oppositeVertex(v);
					if (otherV.isVisited) 
					{
						edge.type = EdgeType.CROSS;
					} 
					else 
					{
						vQueue.enqueue(otherV);
					}
				}
			}
			retSet.add(component);
			
			for (Vertex<V,E> v : vertices)
			{
				if (!v.isVisited)
				{
					vertex = v;
					break;
				}
			}
		}
		
		return retSet;
	}

}
